import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 51. N 皇后
 * https://leetcode.cn/problems/n-queens/description/
 */
class Solution5 {
    List<List<String>> ret;
    char[][] path;
    boolean[] checkCol;
    boolean[] checkDig1;
    boolean[] checkDig2;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        ret = new LinkedList<>();
        n = _n;
        checkCol = new boolean[n];
        checkDig1 = new boolean[2 * n];//主对角线
        checkDig2 = new boolean[2 * n];//副对角线
        path = new char[n][n];

        for(int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }

        dfs(0);

        return ret;
    }

    public void dfs(int row) {
        if(row == n) {
            List<String> list = new LinkedList<>();
            for(int i = 0; i < n; i++) {
                String tmp = new String(path[i]);
                list.add(tmp);
            }
            ret.add(list);
            return;
        }

        for(int col = 0; col < n; col++) {
            if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }
}